package leetcode.editor.cn;

//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 算法的时间复杂度应该为 O(log (m+n)) 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
// Related Topics 数组 二分查找 分治 👍 5309 👎 0

import java.util.Arrays;

//Java：【4】 - 寻找两个正序数组的中位数
public class MedianOfTwoSortedArrays_4{
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays_4().new Solution();
                // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length+nums2.length;
        int[] nums = new int[length];
        int i=0,j=0;
        while (i<nums1.length && j<nums2.length){
            if(nums1[i]<nums2[j]){
                nums[i+j] = nums1[i];
                i++;
            }else{
                nums[i+j] = nums2[j];
                j++;
            }
        }
        while(i<nums1.length) nums[i+j] = nums1[i++];
        while(j<nums2.length) nums[i+j] = nums2[j++];
//        System.out.println(Arrays.toString(nums));
        return length%2==1?nums[length/2]:((double)nums[length/2]+(double)nums[length/2-1])/2;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
